Federal Communications Commission (FCC) has allotted a spectrum of bandwidth in the 60 GHz frequency range (57 to 64 GHz). The Wireless Gigabit Alliance (WiGig) is targeting the standardization of this frequency band that will support data transmission rates up to 7 Gbps. Integrated circuits, formed in semiconductor die, offer high frequency operation in this millimeter wavelength range of frequencies. Some of these integrated circuits utilize Complementary Metal Oxide Semiconductor (CMOS), Silicon-Germanium (SiGe) or GaAs (Gallium Arsenide) technology to form the dice in these designs. The receive path of the signal being transferred in the wireless channel in these communication system need to be compensated for various very dispersive conditions occurring in the wireless channel. Some of these conditions include multipath reflection, multipath resilience, ISI (Inter Symbol Interference), channel capacity, strategies for frequency diversity scheduling, etc.
CMOS (Complementary Metal Oxide Semiconductor) is the primary technology used to construct integrated circuits. N-channel devices and P-channel devices (MOS device) are used in this technology which uses fine line technology to consistently reduce the channel length of the MOS devices. Current channel lengths are 40 nm, the power supply of VDD equals 1.2V and the number of layers of metal levels can be 8 or more.
CMOS offers the computing power to perform many of the required compensation techniques requires overcoming the adverse conditions of the wireless channel. Yet, the computing power must be used in a power efficient manner to insure that the dissipated power is low enough to allow these important building blocks of the transceiver fabricated in CMOS to be used in mobile applications. This helps to insure that the energy drawn from the limited power contained in the battery is minimized while achieving the optimum performance.
Orthogonal frequency division multiplexing (OFMA) is a multi-carrier system that has been used in various communication Standards such as 802.11 (Wi-Fi), digital video broadcasting (DVB), asymmetrical digital subscriber lines (ASDL), etc. However, OFDM suffers from several deficiencies including peak to average power ratio (PAPR), sensitivity to amplifier nonlinearities, and effects of frequency offsets. Single carrier (SC) communication systems, however, overcome these several deficiencies and offer several benefits over OFDM systems.
SC communication systems is a single-carrier transmit signal that partitions their wideband channel into a large number of parallel narrowband subcarriers and has a lower PAPR resulting in design parameters in the transmit path that are simpler to achieve when compared to OFDM.
In the transmitter side as illustrated in FIG. 1, the input signals are mapped 1-2 into symbols, then the symbols are converted from a serial path into parallel blocks with a series to parallel (S/P) converter 1-3 so a cyclic prefix 1-4 can be added to each block. A parallel to serial (P/S) converter 1-5 recombines these blocks into a serial link which is zero padded and filtered 1-6. A digital to analog (D/A) converter 1-7 converts the digital serial link to an analog signal and presented to an analog transmitter 1-8. The signal is sent over the wireless channel 1-9 which time disperses the signal and introduces noise 1-21 into the signal. A receiver front end 1-10 receives the distorted wireless signal and converted to a digital signal with an analog to digital (A/D) converter 1-11. The signal is then filtered 1-12. The prefix is removed 1-13 and a S/P converter 1-14 generates a time domain of parallel block signals that are converter by an fast Fourier transform (FFT) 1-15 in to the frequency domain. A frequency domain equalizer 1-16 is applied to each of the transmitted subcarriers where the channel distortion caused by the channel is compensated for each subcarrier by the frequency domain equalizer. The FFT and frequency domain equalization requires less computation power than an equivalent performing time-domain equalization. An inverse FFT (IFFT) 1-17 generates the time domain representation of the frequency compensated transmitted signal to a de-mapper unit 1-18. The De-mapper feeds its output to a low density parity check (LDPC) decoder 1-22. The LDPC, invented by Gallager “R. G. Gallager, Low Density Parity Check Codes, Cambridge, Mass., MIT Press, 1963., is a well-known linear error code correcting code that approaches the Shannon limit and therefor called a capacity approaching code. After the LDPC, the recovered messages are then applied to a descrambler 1-23 to recover the symbols which are then applied to a P/S converter 1-19. The output signal is applied to the baseband circuitry of the receiver to extract the signals from the transmitter. The combination of the de-mapper, LDPC decoder and de-scrambler is contained within the dotted box 1-24 and will be described in more detail shortly.
A parity-check decoder allows error correction allows messages which are transmitted over a noisy transmission medium to be captured and recovered at a receiver with a noise threshold that can approach the upper bound of the channel noise. These messages comprise codewords [C] that are generated with additional bits for redundancy. These additional bits are called check bits and are placed in the codewords making each codeword distinct from another codeword. This error recovery decoder is required where the codewords as sent by the transmitter are altered in transit to the receiver. The medium which interconnects the transmitter to the receiver can be noisy and can alter the value of the bits contained within the codewords. An example of a hostile medium is a wireless connection between the transmitter and the receiver. Such a wireless medium suffers from noise of the environment, other transmitters in the local area competing for the limited available spectrum, multiple path reflections from buildings and structures, signal loss, and etc.
A Hamming distance separates the codewords from one another and is the number of bit positions that are different. For instance, the codeword [0 1 0 0 1 1 0 1] differs from the codeword [0 1 0 1 0 1 0 0] by three positions: 4th, 5th, and 8th. This large Hamming distance helps to identify the proper codeword during error recovery of a decoder since the decoder would pick the closest one after the algorithm has completed.
A spare matrix H called a parity-check matrix determines the codewords of the source message that satisfies the following equation:HC=0  (EQ. 1)over the Galois field GF(2).
                    H        =                              [                                                            1                                                  1                                                  0                                                  1                                                  0                                                  0                                                                              0                                                  1                                                  1                                                  0                                                  1                                                  0                                                                              1                                                  1                                                  1                                                  0                                                  0                                                  1                                                      ]                    =                      [                          A              ⁢                                                          ⁢                              I                                  n                  -                  k                                                      ]                                              (                  EQ          .                                          ⁢          2                )            where n=length of codeword and k=bits in the message. I is the identity matrix and AThe constraints for the parity-check matrix H are:c0+c1+c3=0;c2+c3+c5=0;c1+c2+c3+c6=0;  (EQ. 3)
A good received codeword at the transmitter satisfies the following equation:HyT=0  (EQ. 4)where yT is the received codeword at the receiver.
A generator is required to create these codewords at the transmitter. Gauss-Jordan elimination on H can be used to find the generator G by inverting [A In-k] to reach [I A−1] or:
                    G        =                              [                                                            1                                                  0                                                  0                                                  1                                                  0                                                  1                                                                              0                                                  1                                                  0                                                  1                                                  1                                                  1                                                                              0                                                  0                                                  1                                                  0                                                  1                                                  1                                                      ]                    =                      [                          I              ⁢                                                          ⁢                              A                                  -                  1                                                      ]                                              (                  EQ          .                                          ⁢          5                )            
The source message S is combined with the parity check bits to generate a codeword C for that source message S at the source. The interconnect medium contributes noise to the message such that the received message Y now contains noise N, or Y=C+N. The spare matrix is known at both the source and destination and the destination and is used to calculate the vector Z=HY=HC+HN at the receiver, and from EQ. 1, Z=HN. This last relationship is used by the decoding process to find the equation which solves HN=Z to determine the noise component n. This noise estimate is subtracted from the received signal y to recover the codeword C. Once the codeword, as sent by the transmitter is recovered at the receiver, the original source message S can be extracted and provided to the transmitter.
Several methods of decoding a LDPC code are available some use the hard values while others use the soft values. The binary erasure channel and bit-flipping decoding use the hard values to determine the value of the corrupted bit. The sum-product decoding method uses soft values. Soft values comprise the sign of the bit values and the magnitude of the bit values, while hard values only look at the sign of the bit value. These iteratively decoding algorithms like the sum-product algorithm are called by different names: the belief propagation algorithm, and the message passing algorithm.
A description of several decoders including the LDPC is provided. Data that has been transmitted satisfies an LDPC code uses a parity-check representation of a binary linear (n, k) block code C where C is the set of all binary n-tuples that satisfy the following (n-k) parity check equation,bHT=0  (EQ. 6)where H is a sparse (n-k) (n) parity check matrix. There are (n) observed bits b, (k) linearly independent generators or constraints in C. The densities of ones in the matrix should be sparse so that the iterative sum-product can be performed quickly to decode the information.
A Tanner graph of a parity check representation for an (8, 4, 4) code is presented in FIG. 2A. This Tanner graph shows a graphical representation of an elementary linear behavior realization of a linear (n, k) block code over Fq of a system and is defined by its trajectories of local constraints. There are (n) variable nodes, (n-k) constraint (zero-sum) nodes which are linearly independent generators in C. The number of edges in the Tanner graph is equal to the number of ones in the parity-check matrix H. These trajectories are the codewords which satisfy those particular constraints. In this graphical representation you could have an observed symbol (n) within the code word. A hidden symbol (u) which represents the state. And you could have the constraints which are the linear homogeneous equations on the subset of the variables.
First the elementary realizations of linear (n, k) block codes over a finite field Fq are illustrated. The code C is the set of all linear combinations Σiuigi over the finite field where the set of generators gj where j is less than or equal to k.
For the (8, 4, 4) code, G is the generator matrix and is shown in EQ. 7, where the n is the number of bits in the codeword, m is the number of parity-check equations, and k is the number of information bits. The code for G is:
                              G          =                      [                                                            1                                                  1                                                  1                                                  1                                                  0                                                  0                                                  0                                                  0                                                                              0                                                  1                                                  0                                                  1                                                  1                                                  0                                                  1                                                  0                                                                              0                                                  0                                                  1                                                  1                                                  1                                                  1                                                  0                                                  0                                                                              0                                                  0                                                  0                                                  0                                                  1                                                  1                                                  1                                                  1                                                      ]                                                                                      ⁢                                                          ⁢                                    b              0                        ⁢                          b              1                        ⁢                          b              2                        ⁢                          b              3                        ⁢                          b              4                        ⁢                          b              5                        ⁢                          b              6                        ⁢                          b              7                                                          (                  EQ          .                                          ⁢          7                )            
the columns are labeled b0 . . . b7 along the top, while the rows would be labeled (not shown) as c1, c2, c3, and c4 from top to bottom. FIG. 2A illustrates the parity-check realization of the generator matrix EQ. 7. The (n) variable nodes are shown on the left range from b0 to b7 and the (n-k) constraints range from ci to c4. Each of the blocks with the (+) calculates the exclusive or of the inputs such that they should equal to zero if the codeword is unaltered.
The set of bits in the j-th parity check equation of the code is determined using the generator matrix G and setting the constraint equations in columns b0 . . . b7 equal to the summation of those positions where the matrix has a one for the state variables; c1, c2, c3, and c as:b0=c1;b1=c1+c2;b2=c1+c3;b3=c1+c2+c3;b4=c2+c3+c4;b5=c3+c4;b6=c2+c4;b7=c4;  (EQ. 8)The Tanner graph of the 4th bit relation of EQ. 8 is depicted in FIG. 2A.
The parity-check equations are determined from EQ. 7 and provides the 4 constraint linear homogeneous equations that summing each row as a function of the 8 constraint variables x0 . . . x7 to zero:x0+x1+x2+x3=0;x1+x3+x4+x6=0;x2+x3+x4+x5=0;x4+x5+x6+x7=0;  (EQ. 9)
At the start of the first cycle, the sum product decoding of LDPC broadcast the bit nodes bi to the check-nodes ci. For example, the b0 equals the intrinsic value y0 received from the channel, the b1 equals the intrinsic value y1 received from the channel, the b2 equals the intrinsic value y2 received from the channel, and the b3 equals the intrinsic value y3 received from the channel as illustrated in FIG. 2B. Each of the values bi received at parity-check nodes ci are used in the parity-check equations to further the calculations. The arrow 2-10 indicates that the movement of data is from the bit-nodes 2-2 to the constraint-nodes 2-3.
For instance in FIG. 2C, the input values: b0, b1, and b2 are sent to parity-check node c1 and are used to calculate the value of c′1. Once calculated, the parity-check c1 2-5 sends the result to the bit node b3 2-4. After bit node b3 receives the value of c′1 calculated by the parity-check c1. The bit-node b3 stores the message of c′1 as E1,3 at bit-node b3. The arrow 2-11 indicates that the movement of data is from the constraint-node 2-5 to the bit-node 2-4.
In FIG. 2D, the input values: b1, b4, and b6 are sent to parity-check node c2 and are used to calculate the value of c′2. Once calculated, the parity-check c2 2-6 sends the result to the bit node b3 2-4. After bit node b3 receives the value of c′2 calculated by the parity-check c2. The bit-node b3 stores the message of c′2 as E2,3 at bit-node b3. The arrow 2-11 indicates that the movement of data is from the constraint-node 2-6 to the bit-node 2-4.
In FIG. 2E, the input values: b2, b4, and b5 are sent to parity-check node c3 and are used to calculate the value of c′3. Once calculated, the parity-check c3 2-7 sends the result to the bit node b3 2-4. After bit node b3 receives the value of c′3 calculated by the parity-check c3. The bit-node b3 stores the message of c′3 as E3,3 at bit-node b3. The arrow 2-11 indicates that the movement of data is from the constraint-node 2-7 to the bit-node 2-4.
A majority-rule is presented in FIG. 2F. Node b3 performs a modulo 2 addition on the values of E1,3, E2,3 and E3,3. In a first case, the result generates a “1” then the extrinsic value of y3 must be a “1” to maintain that overall parity-check of all inputs: E1,3, E2,3 and E3,3, and y3 must generate a “0” to insure that the parity-check condition is maintained. In a second case, if the modulo 2 addition on the values of E1,3, E2,3 and E3,3 results in a “0”, then the extrinsic value of y3 must be a “0” to maintain that overall parity-check of all inputs: E1,3, E2,3 and E3,3, and y3 must generate a “0” to insure that the parity-check condition is maintained. In both cases, if the parity-check condition is maintained, then the extrinsic value is correct. If the parity-check condition is maintained for all bit-node b0-bn, then EQ. 1 is satisfied and the iterative cycle can stop. Otherwise, in the next cycle all the values of the previous cycle regarding the calculation of the modulo 2 addition of all values of Ej,i, at a particular bit-node bi is substituted for yi and the next cycle begins.
The extrinsic message c′j from the parity-check node j to bit-node i is the probability that bit i causes the parity-check at parity-node constraint j to be satisfied when bit i=1. This probability is given as:
                              P                      j            ,            i                    1                =                              1            2                    -                                    1              2                        ⁢                                                            ∏                                                                                                                              c                    i                    ′                                    ≠                                      c                    j                                                              ⁢                              (                                  1                  -                                      2                    ⁢                                          P                                              c                        ′                                            1                                                                      )                                                                        (                  EQ          .                                          ⁢          10                )            where Pc′1 is the current estimate for the bit=1 during the current cycle. The product is taken over the message edges between the bit-node and all connected check-nodes ci. The probability that the parity-check equation is satisfied when bit i=0. This probability is given as:
                              P                      j            ,            i                    0                =                              1            -                          P                              j                ,                i                            1                                =                                    1              2                        +                                          1                2                            ⁢                                                                    ∏                                                                                                                                            c                      i                      ′                                        ≠                                          c                      j                                                                      ⁢                                  (                                      1                    -                                          2                      ⁢                                              P                                                  c                          ′                                                1                                                                              )                                                                                        (                  EQ          .                                          ⁢          11                )            
The log likelihood ratios (LLR) Ej,i is the LLR of EQ. 11 or:
                              E                      j            ,            i                          =                              LLR            ⁡                          (                              P                                  j                  ,                  i                                1                            )                                =                      log            ⁡                          (                                                1                  -                                      P                                          j                      ,                      i                                        1                                                                    P                                      j                    ,                    i                                    1                                            )                                                          (                  EQ          .                                          ⁢          12                )            where the log is loge and using EQ. 10 gives:
                              E                      j            ,            i                          =                  log          ⁡                      (                                                            1                  2                                +                                                      1                    2                                    ⁢                                                            ∏                                                                        c                          i                          ′                                                ≠                                                  c                          j                                                                                      ⁢                                          (                                              1                        -                                                  2                          ⁢                                                      P                                                          c                              ′                                                        1                                                                                              )                                                                                                                    1                  2                                -                                                      1                    2                                    ⁢                                                            ∏                                                                        c                          i                          ′                                                ≠                                                  c                          j                                                                                      ⁢                                          (                                              1                        -                                                  2                          ⁢                                                      P                                                          c                              ′                                                        1                                                                                              )                                                                                            )                                              (                  EQ          .                                          ⁢          13                )            
With the aid of EQ. 12,
                                          1            -                          P                              j                ,                i                            1                                            P                          j              ,              i                        1                          =                  e                      M                          j              ,                              i                ′                                                                        (                  EQ          .                                          ⁢          14                )            solving for Pj,i1 gives:
                              P                      j            ,            i                    1                ,                  =                                    1                              1                +                                  e                                      M                                          j                      ,                                              i                        ′                                                                                                                  =                          (                                                Pr                  ⁡                                      [                                                                  c                        ′                                            =                                              0                        ❘                        y                                                              ]                                                                    Pr                  ⁡                                      [                                                                  c                        ′                                            =                                              1                        ❘                        y                                                              ]                                                              )                                                          (                  EQ          .                                          ⁢          15                )            where Pr[c′=0|y] is the probability of event [c′=0] given the event y and Pr[c′=1|y] is the probability of event [c′=1] given the event y. Determining (1−2Pc′1) gives:
                              (                      1            -                          2              ⁢                              P                                  c                  ′                                1                                              )                =                              1            -                          2                              1                +                                  e                                      M                                          j                      ,                                              i                        ′                                                                                                                          =                                                                      e                                      M                                          j                      ,                                              i                        ′                                                                                            -                1                                                              e                                      M                                          j                      ,                                              i                        ′                                                                                            +                1                                      =                          tanh              ⁡                              (                                                      M                                          j                      ,                                              i                        ′                                                                              2                                )                                                                        (                  EQ          .                                          ⁢          16                )            
Substituting EQ. 16 into EQ. 13 gives:
                              E                      j            ,            i                          =                  log          ⁡                      (                                                            1                  2                                +                                                      1                    2                                    ⁢                                      Π                                                                  c                        i                        ′                                            ≠                                              c                        j                                                                              ⁢                                      tanh                    ⁡                                          (                                                                        M                                                      j                            ,                                                          i                              ′                                                                                                      2                                            )                                                                                                                    1                  2                                -                                                      1                    2                                    ⁢                                      Π                                                                  c                        i                        ′                                            ≠                                              c                        j                                                                              ⁢                                      tanh                    ⁡                                          (                                                                        M                                                      j                            ,                                                          i                              ′                                                                                                      2                                            )                                                                                            )                                              (                  EQ          .                                          ⁢          17                )            
The following is a fundamental logarithmic identity:
                              2          ⁢                                    tanh                              -                1                                      ⁡                          (                                                M                                      j                    ,                                          i                      ′                                                                      2                            )                                      =                  log          ⁡                      (                                          1                +                                  (                                                            M                                              j                        ,                                                  i                          ′                                                                                      2                                    )                                                            1                -                                  (                                                            M                                              j                        ,                                                  i                          ′                                                                                      2                                    )                                                      )                                              (                  EQ          .                                          ⁢          18                )            EQ. 18 can be used in EQ. 17 to provide:
                              E                      j            ,            i                          =                  2          ⁢                                    tanh                              -                1                                      ⁡                          (                                                Π                                                            c                      i                      ′                                        ≠                                          c                      j                                                                      ⁢                                  tanh                  ⁡                                      (                                                                  M                                                  j                          ,                                                      i                            ′                                                                                              2                                        )                                                              )                                                          (                  EQ          .                                          ⁢          19                )            Ej,i is the extrinsic LLR message from each check-node cj to a particular bit-node bi which also receives an a priori LLR from the ith bit position of the input codeword yi. The total LLR of the probability include all the check-nodes satisfying one of the parity-check equations and the ith bit position of the input codeword yi:Li=LLR(Pi1)=ri+Σj∈AiEj,i  (EQ. 20)where ri is the LLR of the a priori of the ith bit position of the input codeword yi:
                              r          i                =                  (                                    Pr              ⁡                              [                                                      c                    i                                    =                                      0                    ❘                    y                                                  ]                                                    Pr              ⁡                              [                                                      c                    i                                    =                                      1                    ❘                    y                                                  ]                                              )                                    (                  EQ          .                                          ⁢          21                )            
The message Mi,j sent from a bit-node bi to check-nodes c′ indicates the LLR excluding the check-node ci and is given as:Mi,j=−ri+Σj≠j′Ej′,i  (EQ. 22)
For a additive white Gaussian noise (AWGN) channel, the a priori LLR is given by
                              r          i                =                              4            ⁢                          y              i                        ⁢                                          E                s                                            N                o                                              =                                    2              ⁢                              y                i                                                    σ              2                                                          (                  EQ          .                                          ⁢          23                )            
Log likelihood ratios (LLR) are used in the sum-product algorithm. Let R have the elements (0,1) in the GF (2) field. The LLR of a binary random variable R, L(r), is then defined as:
                              L          ⁡                      (                          r              i                        )                          =                  log          ⁡                      (                                          Pr                ⁡                                  [                                                            r                      i                                        =                                          0                      ❘                      y                                                        ]                                                            Pr                ⁡                                  [                                                            r                      i                                        =                                          1                      ❘                      y                                                        ]                                                      )                                              (                  EQ          .                                          ⁢          24                )            L(ri) then indicates the probability that the random variable R takes on the value ri. The magnitude of the log-likelihood ratio L(ri) determines the so called “soft” value (αj,i′) of the random variable R while the hard decision is determined by the sign (βj,i′=|Mj,i′|) of the magnitude |L(ri)| and is the reliability of this decision.Substituting
      tanh    ⁡          (                        M                      j            ,                          i              ′                                      2            )        =            (              α                  j          ,                      i            ′                              )        ⁢          tanh      ⁡              (                              (                          β                              j                ,                                  i                  ′                                                      )                    2                )            
                                          Π                                          c                i                ′                            ≠                              c                j                                              ⁢                      tanh            ⁡                          (                                                M                                      j                    ,                                          i                      ′                                                                      2                            )                                      =                              [                                          Π                                                      c                    i                    ′                                    ≠                                      c                    j                                                              ⁢                              α                                  j                  ,                                      i                    ′                                                                        ]                    ⁡                      [                                          Π                                                      c                    i                    ′                                    ≠                                      c                    j                                                              ⁢                              tanh                ⁡                                  (                                                            β                                              j                        ,                                                  i                          ′                                                                                      2                                    )                                                      ]                                              (                  EQ          .                                          ⁢          25                )            Placing EQ. 25 into EQ. 19 gives:
                              E                      j            ,            i                          =                              [                                          Π                                                      c                    i                    ′                                    ≠                                      c                    j                                                              ⁢                              α                                  j                  ,                                      i                    ′                                                                        ]                    ⁢          2          ⁢                      tanh                          -              1                                ⁢                      log                          -              1                                ⁢                      log            ⁡                          [                                                Π                                                            c                      i                      ′                                        ≠                                          c                      j                                                                      ⁢                                  tanh                  ⁡                                      (                                                                  β                                                  j                          ,                                                      i                            ′                                                                                              2                                        )                                                              ]                                                          (                  EQ          .                                          ⁢          26                )            distributing the log−1 log term provides:
                              E                      j            ,            i                          =                              [                                          Π                                                      c                    i                    ′                                    ≠                                      c                    j                                                              ⁢                              α                                  j                  ,                                      i                    ′                                                                        ]                    ⁢          2          ⁢                      tanh                          -              1                                ⁢                                    log                              -                1                                      ⁡                          [                                                Π                                                            c                      i                      ′                                        ≠                                          c                      j                                                                      ⁢                log                ⁢                                                                  ⁢                                  tanh                  ⁡                                      (                                                                  β                                                  j                          ,                                                      i                            ′                                                                                              2                                        )                                                              ]                                                          (                  EQ          .                                          ⁢          27                )            The sum-product algorithm of the LDPC can be further simplified by partitioning the LLR ratio into a magnitude component and a sign component. Furthermore, a product term can be replaced with an additive term by utilizing logarithms.
                              ψ          ⁡                      (                          β                              j                ,                                  i                  ′                                                      )                          =                  log          ⁡                      (                          tanh              ⁢                                                                                    β                                          j                      ,                                              i                        ′                                                                              2                                                                      )                                              (                  EQ          .                                          ⁢          28                )            and solving for βj,i′ in EQ. 28 provides:βj,i′=2 tan h−1 log−1 [ψ(βj,i′)]  (EQ. 29)substituting EQ. 28 and EQ. 29 into EQ. 27 leaves:Ej,i=[Πci′≠cjαj,i′]2 tan h−1 log−1 [Σci′≠cjψ(βj,i′)]  (EQ. 28)and
                              tanh          ⁢                                                                β                                  j                  ,                                      i                    ′                                                              2                                                  =                              log                          -              1                                ⁢                      ψ            ⁡                          (                              β                                  j                  ,                                      i                    ′                                                              )                                                                      where solving for βj,i′ gives:Ej,i=−[Πci′≠cjαj,i′]ψ[Σci′≠cjψ(βj,i′)]  (EQ. 29)
The final equations that are used are arrived at by setting Rj,i=Ej,i; βj,i′=L(qj,i′); αj,i′=sign L(qj,i′); in EQ. 29:Sj,i=[Πci′≠cjαj,i′]=Πci′≠cj[signL(qj,i′)]  (EQ. 30)andAj,i[Σci′≠cjψ(βj,i′)]=Σci′≠cjψ(L(qj,i)  (EQ. 31)Rj,i=−Sj,iψ[Aj,i]  (EQ. 32)setting Σj∈Ai Ej,i=L(qj,i); ri=Rj,i; Li=L(qj)=Mi,j; EQ. 20 becomes:L(qj,i)=L(qj)−Rj,i  (EQ. 33)Using EQ. 22, and EQ. 23, the message Mi,j sent from a bit-node bi to check-nodes c′ indicates the LLR excluding the check-node cj and is given as:
                              L          ⁡                      (                          q              j                        )                          =                                            2              ⁢                              y                i                                                    σ              2                                +                                    Σ                              j                ≠                                  j                  ′                                                      ⁢                          R                              j                ,                i                                                                        (                  EQ          .                                          ⁢          34                )            
The received bits represent probabilities at each bit node or input node. These bit-nodes are combined with the constraints-nodes in a Tanner graph to perform the belief propagation procedure. In the first iteration, these probabilities are passed from the bit-nodes to the constraint-nodes and are updated according to the parity check constraints. These values become updated and the new probabilities are send back to the symbol nodes which also performs the parity check constraint. At the bit-nodes, the values are again updated and if EQ. 4 is satisfied, then the process stops; otherwise, the recalculated probabilities at each bit-node or input nodes are passed from these bit-nodes to the constraint-nodes again in additional iterative manner and are updated according to the parity check constraints. These newer values become updated and the newer probabilities are send back to the symbol nodes which also performs the parity check constraint again. Then, at the bit-nodes, the values are again updated and if EQ. 4 is satisfied, the process is stopped and the correct codewords have been determined. The source message can then be extracted from the codeword.
FIG. 3A and FIG. 3B illustrate a generator realization and parity-check realization for the (8, 4, 4) code. FIG. 3A illustrates the b1 to b7 bit values 2-2 broadcast their value to the parity-check 2-3 so that these blocks can compute the sum-product constraint. Once the sum-product constraint has been computed, the network then causes the newly calculated c1 to c4 parity bit values 2-5 to send their value to the (n) symbols 2-4. The majority rule calculates the bit values in a second cycle. The flip from a generator realization to a parity-check realization is understood by comparing FIG. 3A and FIG. 3B. Now the (n) symbols are broadcast back to the (n-k) constraints once the (n-k) constraints have calculated their value, the network flips back to a generator realization and continually does an iterative loop until the number of loops is exceeded beyond a set value or the values of the (n) symbols x0 through x7 have arrived at their final value.
FIG. 4A illustrates the (n) symbols being in the broadcast mode are coupled to an interleaver block also known as a π network. The interleaver block then couples to the (n-k) constraints being in the zero-sum mode. The number of ports arriving from the (n) symbols to the interleaver is PL while the number of ports between the interleaver and the (n-k) constraints is PR. The interleaver requires that PL equals PR to operate properly.
FIG. 4B illustrates a trellis block diagram for another decoding system called the Belief Propagation decoder and algorithm. This figure illustrates the flow of messages and computations using a sum-product algorithm to calculate the values. The values x0 to xn generate the input messages i0-in which are the intrinsic a posteriori probabilities (APP) vectors derived from the observation. The output messages eo-en are the extrinsic APP vectors and are provided at x0 to xn. The blocks Co-Cn 4-2 capture the intrinsic data and proceeds to independently calculate the forward (α1 to αn) and backwards (βn to β1) directions simultaneously. In the forward direction, the messages flows from C0 to Cn while in the backwards direction the messages flows from Cn to C0. Once the forward message reaches Cn and the backward message reaches C0, the BCJR algorithm is complete and the extrinsic data is output to x0-xn. This algorithm uses a sum-product rule within each of the blocks Co-Cn 4-2.